
package com.annvcit.graph;

import java.util.Random;
import java.util.Stack;


/**
 * @author annvcit
 * @full_name Nguyen Van Chuc An
 * @date_created Dec 16, 2014
 * @email annvcit@gmail.com
 */
public class UndirectedGraph extends AGraph{

	public UndirectedGraph(String fileName) {
		super(fileName);
	}

	public UndirectedGraph(int[][] am, int verties) {
		super(am, verties);
	}

	// tính bậc của đỉnh cho trước
	public int deg(int v) {
		int deg = 0;
		for (int i = 0; i < verties; i++) {
			deg += adjMtrx[v][i];
		}
		return deg;
	}
	
	// tính số cạnh của đồ thị
		public int edges() {
			int edges = 0;
			for (int i = 0; i < verties; i++) {
				edges += deg(i);
			}
			return edges / 2;
		}
		
		// đếm số thành phần liên thông
		public int countConnectedComponents() {
			int tplt = 0;
			boolean[] visited = new boolean[verties];
			Stack<Integer> stack = new Stack<>();
			int dinhKe;
			int v1;
			
			while (true) {
				v1 = -1;
				// tìm một đỉnh chưa được th
				for (int i = 0; i < verties; i++) {
					if (!visited[i]) {
						v1 = i;
						visited[v1] = true;
						stack.add(v1);
						tplt++;
						break;
					}
				}
				
				if (v1 == -1) break;
				
				// bắt đầu từ v1, tìm tất cả các đỉnh trong tplt của nó & đánh dấu
				while (true) {
					dinhKe = -1;
					// tìm đỉnh kề của v1
					for (int i = 0; i < verties; i++) {
						if (adjMtrx[v1][i] != 0 && !visited[i]) {
							dinhKe = i;
							v1 = i;
							visited[dinhKe] = true;
							stack.add(dinhKe);
							break;
						}
					} // end for
					
					// trường hợp không tìm thấy dinhKe nào
					if (dinhKe == -1) {
						// stack chưa empty thì pop ra
						if (!stack.isEmpty()) {
							v1 = stack.pop();
						} else {
							// không còn gì trong stack nữa thì stop program
							break;
						}
					}
				} // end while
			} // end while
			
			return tplt;
		}
		
		public boolean isConnected() {
			return this.countConnectedComponents() == 1;
		}

		@Override
		public void removeEdge(int v1, int v2) {
			adjMtrx[v1][v2]--;
			adjMtrx[v2][v1]--;
		}
		
		// tim mot thanh phan lien thong
		public StringBuilder timMotTplt() {
			StringBuilder tplt = new StringBuilder();
			boolean[] visited = new boolean[verties];
			Stack<Integer> stack = new Stack<>();
			int dinhKe;
			// chon 1 dinh bat dau
			int v1;
			Random rd = new Random();
			v1 = rd.nextInt(verties);
			
			visited[v1] = true;
			stack.add(v1);
			tplt.append(v1);
			
			while (true) {
				dinhKe = -1;
				// tìm đỉnh kề của v1
				for (int i = 0; i < verties; i++) {
					if (adjMtrx[v1][i] != 0 && !visited[i]) {
						dinhKe = i;
						v1 = i;
						visited[dinhKe] = true;
						stack.add(dinhKe);
						tplt.append(dinhKe);
						break;
					}
				} // end for
				
				// trường hợp không tìm thấy dinhKe nào
				if (dinhKe == -1) {
					// stack chưa empty thì pop ra
					if (!stack.isEmpty()) {
						v1 = stack.pop();
					} else {
						// không còn gì trong stack nữa thì stop program
						break;
					}
				} 
			}// end while
			return tplt;
		}
		
}
